package com.gorkr.hot100.medium;

/**
 * @author 张心宇 <zhangxinyu20@kuaishou.com>
 * Created on 2023-01-10
 */
public class M238ProductOfArrayExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] leftDp = new int[length];
        int[] rightDp = new int[length];
        leftDp[0] = 1;
        rightDp[length-1] = 1;
        for (int i = 1; i < length; i++) {
            leftDp[i] = nums[i-1] * leftDp[i-1];
        }
        for (int i = length-2; i >= 0; i--) {
            rightDp[i] = nums[i+1] * rightDp[i+1];
        }
        int[] res = new int[length];
        for (int i = 0; i < length; i++) {
            res[i] = leftDp[i] * rightDp[i];
        }
        return res;
    }
}
